(1) Field of the Invention
This invention relates to a system for scheduling multiple events. More particularly, the invention relates to a system for scheduling multiple events in view of a series of constraints imposed upon the schedule. Still more particularly, the present invention describes a system for scheduling multiple events while at the same time optimizing some user-defined measure of the schedule's quality, such as time to complete the schedule or cost to complete the schedule.
(2) Description of the Prior Art
Scheduling problems are exemplified by the traditional traveling salesman problem (TSP). The goal of the TSP is to find the minimal cost tour of n cities in which a salesman visits each city exactly once and returns to the starting city at the end of the tour. The time dependent TSP (TDTSP) is a variant of the TSP in which the salesman must still visit each city, but the cost of traveling from one city to the next depends on both the distance between cities and the time of day when the travel takes place. When solving the TDTSP, a city—or “node”—is typically designated the “depot” node, where the salesman begins and ends his tour.
Many real-world instances of the TDTSP are concerned with scheduling time-dependent tasks, including the process of scheduling manufacturing jobs on a machine with time-dependent setup costs. One special instance of the TDTSP, known as the deliveryman problem (DMP), has been used to route guided vehicles through a manufacturing system. Other applications of the TDTSP include routing data through a network, creating timetables for university exams, and scheduling vehicles and crews.
Certain properties exploited in TSP heuristics cannot be extended to the TDTSP. Thus, different heuristics are needed to generate solutions to general TDTSPs with more than a few dozen cities.
One approach to solving both the TSP and TDTSP is the adoption of enumerative or so-called “brute force” methods. These methods simply search (i.e., enumerates) every possible solution within the solution space. The obvious drawback to these methods is that they are not practical for most real-world problems, as the search space is too large to be enumerated.
Another method is the random search. Because a random search cannot efficiently save every promising solution it finds, simple random searches do no better than enumerative schemes. While random searches can search a large space effectively, they lack the tools necessary to exploit the more promising areas of that space.
Malandraki and Daskin described several straightforward modifications of the TSP heuristic to the TDTSP, including the standard nearest-neighbor (NN), a variation, known as NN2 that evaluates the cost of paths when each city is guaranteed to be the first city visited after leaving the depot, and a probabilistic nearest neighbor heuristic (NNR) that selects the next city to be visited randomly, according to a user-defined probability function. Test results on problems of up to 25 cities indicate that NN2 performs the best of the three heuristics.
Various heuristics based on mixed integer linear programming (MILP) formulations have also been proposed for the TDTSP. Vander Weil and Sahinidis separate the TDTSP into two sub-problems: one sub-problem containing additional constraints that place an upper bound on the travel cost; and the other sub-problem containing additional constraints that form a lower bound. The algorithm attempts to solve each sub-problem and terminates when the upper and lower bounds are within some user-defined value. Malandraki and Daskin disclose a MILP relaxation technique that removes many of the constraints found in the exact MILP formulation and then adds the constraints back as feasible solutions are found. The algorithm then re-solves the equations to see if the constraints hold, and the process continues until either no constraints remain or one of the constraints is violated.
Malandraki and Dial describe a heuristic based on an exact dynamic programming algorithm that generates good solutions to TDTSPs of up to 55 cities using relatively little processor time, and the quality of the solutions are superior to that of the MILP relaxation technique.
The scheduling systems of the prior art are ponderous and require large amounts of storage space and central processing unit (CPU) time, thus making them costly and inefficient. Therefore, what is needed is a scheduling system that is capable of solving TSPs and TDTSPs economically. What is also needed is a scheduling system that can—based upon the parameters and constraints present in the schedule—select the most appropriate heuristic for solving scheduling problems.